/**
 * 链表: 单向链表, 双向链表, 环形链表
 * 问题:
 * > 链表在头部添加元素更加方便, 数组从尾部添加更方便
 * > 特殊处理在链表操作中非常常见,  一个小技巧: 设计一个 dummyHead 虚拟头节点, 让第一个Node并不为null, 代码逻辑可以简化很多
 *
 * @param <E> 泛型参数
 */
public class OldLinkedList<E> {

    private class Node {
        public E elem;
        public Node next;

        public Node(E elem, Node next) {
            this.elem = elem;
            this.next = next;
        }

        public Node(E elem) {
            this(elem, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return elem.toString();
        }
    }

    private Node head;
    public int size;

    public OldLinkedList() {
        head = null;
        size = 0;
    }

    public void addFirst(E elem) {
        add(0, elem);
    }

    // 实践中, 使用链表时, 通常就不使用索引了
    public void add(int index, E elem) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("index must be between 0 and " + size);
        }
        if (index == 0) { // 第一个节点的元素比较特殊
            // Node node = new Node(elem);
            // node.next = head;
            // head = node; => 等价代码

            head = new Node(elem, head);
            size++;
            return;
        }

        Node prev = head;
        for (int i = 0; i < index - 1; i++) { // prev -> index - 1 位置
            prev = prev.next;
        }

        prev.next = new Node(elem, prev.next);
        size++;
    }

    public void addLast(E elem) {
        add(size, elem);
    }

    @Override
    public String toString() {
        return "";
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}
